COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file
C00003 00003	.hd206 SPRING 1978
C00007 00004	.<< Transforming LISP programs >>
C00013 00005	.if false then begin "other LISP systems"
C00016 00006	.<< Proving >>
C00018 00007	.<<FOL projects>>
C00020 00008	.<< Document compiler>>
C00021 ENDMK
C⊗;
.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file;
.
.MACRO  hd206 (TERM) ⊂
.BEGIN    NOFILL  TURNON "←→"
.place heading
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY
.place text
CS206  ←COMPUTING WITH SYMBOLIC EXPRESSIONS  →TERM
.TURNOFF
.END ⊃
.LSPFONT
.basicops 
.itemmac 1;
.
.PORTION MAINPORTION
.hd206 SPRING 1978
.PAGE ← 1
.cb TERM PROJECTS

	A term project is not required in order to pass CS206 or even to
get a grade of B if your homework and exams are good enough.  However, if
you wish to get some flavor of A then doing a good term project is necessary.
Term projects will be due on the day of the final exam.  Any term project
turned in ahead of time will be likely to get a more thorough reading.

	The term project is your opportunity to direct your attention
to and get experience in some area that interests you.   Briefly
the possibilities include writing and documenting an substantial
LISP program, proving the correctness of a moderate sized LISP program
using FOL and the techniques of Chapter III, or to join an on going
project and write code for some piece of a larger system.  (Richard
Weyrauch(RWW) and Bob Filman(REF) at the AI Lab are willing to have students
join projects they are working on at the lab or provide guidance
in some other projects.   Such projects these are
by references to RWW and REF.)

	The write up of your project is the main thing that will get
graded so it should be clear and carefully done.  It should include
a brief description of what you set out to do and what you accomplished.
If you write a progam, you should give a description of how it works
and why, including a description of the data structures it is acting
on and the basic operations on these structures.  The code
for the program should be included with brief comments in appropriate
places to guide the reader.  Some sample runs should also be included.
If you do a formal proof, you should include a brief description
of the program(s) you are proving things about, an informal proof
mentioning the key steps, and the formal proof (which can be
generated by FOL). 

	The following are some ideas for term projects.  You may choose
one of these, or design your own project.
.<< Transforming LISP programs >>
.bb LISP programs 

#. Improve the LCOM4 compiler.  Some possibilities are to modify LCOM4 to:
.begin nofill 

	##. compile  ⊗label. 
	##. handle the %3prog%1 and related features.
	##. handle functions as arguments (as for ⊗mapcar) .
	##. recognize iteration and compile it with loops.
	##. produce more efficient arithmetic code.
	##. generate more efficient code in other cases where you might have noticed inefficiencies. 
        ##. compile additional features such as "while's" or "do's" etc..
.end
#. Write a program that converts a function definition in to an iterative
form for some class of definitions, or improves the efficiency of some
class of programs.  For example consider the two definitions of ⊗factorial 
.begin nofill

⊗⊗⊗fact n ← qif n=0 qthen 1 qelse n q* fact n-1⊗
and
⊗⊗⊗fact n ← facti[n,1] ⊗
where
⊗⊗⊗facti[n,m]← qif n=0 qthen m qelse facti[n-1,nq*m]⊗
.end
the latter is form is ⊗iterative and could easily be expressed as a loop.
More impressive is the saving when you transform the obvious definition
of the function to compute Fibonacci numbers into iterative form.
.begin nofill

⊗⊗⊗fib n ← qif n=0∨n=1 qthen 1 qelse [fib n-1] + [fib n-2]⊗
vs
⊗⊗⊗fib n ← fibi[n,1,1]⊗
where
⊗⊗⊗fibi[n,k,l] ← qif n=0∨n=1 qthen l qelse fibi[n-1,l,k+l]⊗
.end
The first version makes O(⊗⊗fib n⊗) calls to itself while the latter
makes only O(⊗⊗n⊗).  

	For ideas on improving efficiency consider the various definitions
of ⊗reverse and ⊗fringe given in Chapter I.

#. Extend the notion of purifiable LISP term in some useful and non-tirival
way.  Write a program that tests for purifiability. Write a
program that produces pure terms from purifiable (in the extended sense) ones.
(See Chapters IV and V.)

#. Improve MACLISP at LOTS.  The idea here is to write a program
to help people use LISP.  For example

	##. Write a LISP tutor.  This would be a program that could
be loaded into MACLISP and would explain some of the features of LISP
and then ask the user questions and check the answers.  Choose a few
features that interest you and do them thoroughly, or get together
with a group of students and divide up the work.  In the latter
case it should be clear who did which pieces, although co-operation
is essential.  

	##.  Write a HELP program that would allow the user to ask
for HELP on some collection of topics and give useful information
on those topics.  The topics might include a partial list of available
functions, i/o conventions, debugging facilities, etc.

	##.  Write some editing, file manipulating, i/o or other
programs to do the things you wanted to be able to do but couldn't
when you started using MACLISP at LOTS.

	The tutor and HELP programs will require a lot of thought and
understanding of how LISP works and knowing what is really useful,
but the actual programming should not be very difficult.
Any good projects of the above nature could be compiled and put on
the system for the benefit of future users.

#. Write a program to play a game.  Some possible games are:
.begin nofill

	##. 3-dimensional Tic Tac Toe (See Chapter II for 2-D version)
	##. Solitare
	##. Go (RWW and REF have ideas for interesting projects)
.end
    Be sure to hold individual test runs to a few seconds.  It is easy to
use large amounts of computer time in such projects.  
.if false then begin "other LISP systems"

proof checker
proof strategy trier (interpreter)
problem solving strategy interpreter

MATHLAB at Stanford, trigonometric identity proof checker,
contour integration proof checker,
improvements to REDUCE (e.g. better matrix package, better
matrix inversion, better error messages, (call Hearn),
improved simplification heuristics), display of mathematical
exprssions and their entry using the display (Hearn)
Collins gcd for polynomials, Berlekamp algorithms,


	It is often more convenient to describe certain kinds of
computation with symbolic expressions by "syntax transformations"
than by recursive LISP functions.  For example, consider the
simplification of expressions in a binary  PLUS  and  TIMES  where
the number  0  is to be eliminated from sums, the number  1  is to
be eliminated from products, products containing  0  are to be
replaced by  0, and sums and products of one element are to be
replaced by that element.
This may be accomplished by the function  simplifya  defined by

.begin nofill
	simplifya e ← ↓_if at_↓ e ↓_then_↓ e
			↓_else_↓ {simplifya ↓_ad_↓ e,simplifya ↓_add_↓ e}
			[λwz. ↓_if a_↓ e ↓_eq_↓ PLUS ↓_then_↓
				[↓_if_↓ w = 0 ↓_then_↓ z
				↓_else if_↓ z = 0 ↓_then_↓ w
				↓_else <PLUS w z>]
				↓_else if_↓ w = 0 ∨ z = 0 ↓_then_↓ 0
				↓_else if_↓ w = 1 ↓_then_↓ z
				↓_else if_↓ z = 1 ↓_then_↓ w
				↓_else_↓ <TIMES w z>.
.end
.end "other LISP systems"
.<< Proving >>
.bb Ideas for projects emphasizing proving.
.item←0
#. Prove the correctness or other interesting property of a moderate size
LISP function and formalize your proof using  FOL.   For example
Exercise_3 of Chapter_III would be suitable.  Or you may write your own fucntion
and specifications. (See Appendix A for an example of a FOL proof.)

#.  Develop the theory of re-entrant list structures.  (see Chapter IV.)
Decide on a representation
of such structures as ordinary lists (say with pointers and labels).  Define
some primitive operations (for example: ⊗⊗car cdr cons point cut⊗).  Write programs
to go from one representation to the other.  Write an equality predicate in
for structures in your representation.   Work out an induction schema to
allow you to tell when programs on such structures will terminate.
Write some interesting programs on such structures and prove some facts
about them.
.<<FOL projects>>
.bb Work on the FOL project 
.item←0
	(See RWW or CLT for more details or ideas)
.begin nofill

#.  DEFINITIONS: Implement commands to make and unmake definitions.
#.  DECISION PROCEDURES:
	##. real closed fields
	##. word problem for semigroup semi-decider.
	##. decide plane geometry.
#.  WFF MANIPULATION:
	##. conjunctive normal form
	##. disjunctive normal form
	##. prenexization
        ##. recognize well-formedness in a particual environment
	##. prefix complexity minimalization???
#.  ARITHMETIC EXPRESSION SIMPLIFICATION:
	##. define a normal form and write code that puts a term in this form
	##. reduction of an "=" or "≤" term to simpler form
	##. rewriting and "=" or "≤" term using a list of facts which have the same form.
#.  STATISTICAL ROUTINES FOR FOL:
	##. frequency of GC
	##. memory management statistics
	##. record of usage
#.  LAMBDA EXPRESSION MANIPULATION

.end
.<< Document compiler>>
.bb Other projects to join.
.item←0

#.  Document compiler.  REF has primitive routines and ideas for writing
a document compiler in LISP (PUB POX RUNOFF are document compilers).
RWW also has ideas about writing document compilers.
Pieces of this would make an interesting project.

#.  RWW and CLT and others are working on a music compiler in LISP.  If
you are interested in computer music there are pieces of this that 
would make interesting term projects.